package String;

public class _5_LongestPalindromicSubstring {
    //over time limited
    String res = "";
    public String longestPalindrome_w(String s) {
        if(s.equals("")) return "";
        StringBuffer sb = new StringBuffer(s);
        if (sb.reverse().toString().equals(s)) {
            return s;
        }
        String sl = longestPalindrome_w(s.substring(0, s.length() - 1));
        if (!sl.equals("") &&s.length()>res.length()) {
            res = sl;
        }
        String sr = longestPalindrome_w(s.substring(1,s.length()));
        if (!sr.equals("") && s.length() > res.length()) {
            res = sr;
        }
        return res;
    }

    public String longestPalindrome(String s) {
        String res = "";
        int length = 0;
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome(s, i - length - 1, i)) {
                res = s.substring(i - length - 1, i + 1);
                length += 2;
            } else if (isPalindrome(s, i - length, i)) {
                res = s.substring(i - length, i + 1);
                length += 1;
            }
        }
        return res;
    }

    public boolean isPalindrome(String s, int begin, int end) {
        if(begin<0) return false;
        while (begin < end) {
            if(s.charAt(begin++)!=s.charAt(end--)) return false;
        }
        return true;
    }
}
